#pragma once
#include <stdlib.h>
#include <vector>
#include <assert.h>

using namespace std;



#ifdef	_COMB_UNIT_TEST_CASES
#include "g:\Projects\unit-test-case-environment\src\UnitTestCaseSet.h"
#endif

using namespace constants;
namespace real
{
    class BackwardNode
    {
    /* This class represents the BackwardNode of the tree formed during the forward
    ** sweep. It stores a value, v. g is a vector for storing partial derivatives.
    ** The number of times the BackwardNode is referenced
    ** is stored in the resource counter, rc.
    */
    private:
	_base_number m_v;
	row_container m_g;
	int m_rc;

    public:
	BackwardNode(const _base_number& x = 0.0):m_v(x),m_rc(1){}
	~BackwardNode();
	void touchg(int n){m_g.resize(n);}
	_base_number value( void ) const { return m_v; }
	_base_number deriv(const int idx){ return m_g[idx]; }
	size_t size() const { return m_g.size( ); }
	int rc( ) const { return m_rc; }
	int inc_rc() { return ++m_rc; }
	int dec_rc() { return --m_rc; }
    };
    class BackwardOp
    {
    /* This class is the baseclass of all operation met during the forward
    ** sweep. It contains a pointer to a BackwardNode where the result of the operation
    ** is stored, val.
    */
    protected:
        BackwardNode *val;
        BackwardOp():val(NULL){ }
	BackwardOp(const _base_number &x){
            val = new BackwardNode(x);
        }
	BackwardOp(const BackwardOp &x){
            val = x.val;
            inc_rc( );
        }

    public:
	virtual ~BackwardOp(){
            dec_rc( );
        }
	void inc_rc( ) const {
            assert(val);
            val->inc_rc();
        }
	virtual void dec_rc()   {
            if (val && val->dec_rc()==0)
            {
                /* When no operator refers to a BackwardNode
                 * it can be deallocated. */
		delete val;
		val=0;
            }
        }

    virtual BackwardOp* copy() const = 0;
	virtual void propagate() = 0;
	virtual void propagateop() = 0;
    };
}


namespace combos
{
    row_container* nextPascalTriangleRow(row_container* previous_row)
    {
            assert(previous_row->size( ) >= 2);
            row_container* newRow = new row_container(previous_row->size() + 1);
            (*newRow)[0] = (*newRow)[newRow->size( )-1] = unit( );
            for(size_t i=1; i < newRow->size( ) / 2; i++)
                (*newRow)[newRow->size( )-i-1] = (*newRow)[i] = (*previous_row)[i] + (*previous_row)[i - 1];
                if (newRow->size( ) % 2){
                    int j = newRow->size( )/2;
                    (*newRow)[j] = (*previous_row)[j] + (*previous_row)[j - 1];
                }
            return newRow;
    }


    _base_number C(int n, int k)
        {
            assert(n >= k &&  k >= 0);
            if (n == 0 || n == 1) return unit( );
            row_container* vec = new row_container(2);
            (*vec)[0] = (*vec)[1] = unit( );

			for(int i = 2; i<=n ; i++)
			{
				row_container * newVec = new row_container;
				for(int j=0; j<= min(i, k); j++){
                if (j ==  0 || j == i) newVec->push_back( 1.0 );
                else {
                    _base_number val = (*vec)[j-1] + (*vec)[j];
                    if (val < 0.0) throw "overflow";
                    newVec->push_back(val);
                }
            }
            delete vec;
            vec = newVec;
          }
        _base_number result_value = (*vec)[k];
        delete vec;
        return result_value;
    }//end binomialCoefficient

}

#ifdef	_COMB_UNIT_TEST_CASES
	using namespace combos;
    using namespace unit_tests;
    class CombUnitTestCases : public UnitTestCase{
	static int slowBinomial(int n, int k)
	{
		if (k == 0 || n == k) return 1;
		return slowBinomial(n - 1, k - 1) + slowBinomial(n - 1, k);
	}

public:
    static bool nextPascalTriangleRowTest( )
    {
        //This test tests the nextRow function
		//by printing a pascal triangle. You know if
		//the test failed or succeedeed by looking at it
		row_container * fstRow = new row_container(2);
        (*fstRow)[0] = (*fstRow)[1] = unit( );
		cout<<endl<<"0:    1"<<endl<<endl;
        for(int i=1; i < ten( ); i++){
            cout<<i<<":    ";
            for(size_t j=0; j < fstRow->size( ); j++)
                cout << (*fstRow)[j]<<"  ";
            cout<<endl<<endl;
			row_container * nxtRow = nextPascalTriangleRow(fstRow);
            delete fstRow;
            fstRow = nxtRow;
        }
        delete fstRow;
        return true;
    }
    static bool binomialTest1( )
    {
        bool res = true;
        for(int n = 0; n <= 10; n++)
            for(int k=0; k<=n; k++){
                double slowValue = (double)slowBinomial(n,k);
		double fastValue = C(n,k);
		if (!myAssert::assertDoubleEqu(slowValue, fastValue,
                    "binomialTest:- probabilityUtils::binomialCoefficient", "error", myAssert::verbose)){
                        cout<< slowValue<<" "<<fastValue<<endl;
                        res = false;
		}
            }
        return res;
    }
    static bool binomialTest2( )
    {
        string testDescription("binomialTest2:- probabilityUtils::binomialCoefficient");
        bool res1 = myAssert::assertIntEqu(C(5, 2), 10, testDescription, "error 1", myAssert::verbose);
        bool res2 = myAssert::assertIntEqu(C(7, 3), 35, testDescription, "error 2", myAssert::verbose);
        return (res1 && res2);
    }

   
	CombUnitTestCases( ){
        test_case_methods.push_back( &nextPascalTriangleRowTest );
        test_case_methods.push_back( &binomialTest1 );
        test_case_methods.push_back( &binomialTest2 );
    }
};
#endif
